package com.tgy.algorithm._经典题目01;

public class _017_最长公共子序列 {

    public static int maxSubSeq(String strOne,String strTwo) {

        if (strOne == null || strOne.length() == 0
                || strTwo == null || strTwo.length() == 0) {
            return 0;
        }

        char[] oneChars = strOne.toCharArray();
        char[] twoChars = strTwo.toCharArray();
        int oneLen = oneChars.length;
        int twoLen = twoChars.length;

        int[][] caches = new int[oneLen][twoLen];

//        boolean flag = false;
        caches[0][0] = oneChars[0] == twoChars[0] ? 1:0;
        for (int i = 1; i < twoLen; i++) {
            caches[0][i] = oneChars[0] == twoChars[i] ? 1:caches[0][i - 1];
        }

        for (int i = 1; i < oneLen; i++) {

            caches[i][0] = twoChars[0] == oneChars[i] ? 1:caches[i - 1][0];
        }

        for (int i = 1; i < oneLen; i++) {
            for (int j = 1; j < twoLen; j++) {
                int maxValue = Math.max(caches[i - 1][j],caches[i][j-1]);
                if (oneChars[i] == twoChars[j]) {
                    caches[i][j] = Math.max(caches[i - 1][j - 1] + 1 ,maxValue);
                }else {
                    caches[i][j] = maxValue;
                }
            }
        }

        return caches[oneLen - 1][twoLen - 1];
    }

    public static int maxSubSeq01(String strOne,String strTwo) {

        if (strOne == null || strOne.length() == 0
                || strTwo == null || strTwo.length() == 0) {
            return 0;
        }

        char[] oneChars = strOne.toCharArray();
        char[] twoChars = strTwo.toCharArray();
        int oneLen = oneChars.length;
        int twoLen = twoChars.length;
        return doMaxSubSeq01(oneChars,twoChars,oneLen - 1,twoLen - 1);
    }

    public static int doMaxSubSeq01(char[] oneChars,char[] twoChars, int i, int j) {

        if (i == 0 && j == 0) {
            return oneChars[i] == twoChars[j] ? 1:0;
        }

        if (i == 0) {
            // j != 0
            return oneChars[0] == twoChars[j] ? 1: doMaxSubSeq01(oneChars,twoChars,i,j - 1);
        }

        if (j == 0) {
            // i != 0
            return twoChars[0] == oneChars[i] ? 1: doMaxSubSeq01(oneChars,twoChars,i - 1,j);
        }

        int ret01 = doMaxSubSeq01(oneChars, twoChars, i - 1, j);
        int ret02 = doMaxSubSeq01(oneChars,twoChars,i,j - 1);
        int ret = Math.max(ret02,ret01);
        if (oneChars[i] != twoChars[j]) {
            ret = Math.max(ret,doMaxSubSeq01(oneChars,twoChars, i - 1, j - 1) + 1);
        }

        return ret;
    }

    public static void main(String[] args) {
        String one = "abfbc";
        String two = "bbac";
//        int maxed = maxSubSeq(one, two);
        int maxed = maxSubSeq01(one, two);
        System.out.println(maxed);
    }
}
